/// 查找奇合数不能写成一个素数和一个平方的两倍之和的结构体。
/// 判断start是否是一个奇合数，可以采用5,7,9, 11, 13, 15 ...依次判断是不是合数
/// 可以优化一下，减少判断的次数，采用(5 + 6i)的分块形式,5(i=0)，7，9，11(i=1)，13, 15, 17(i=2),...
/// 上面的9和15都是奇合数，有没有办法不用判断，直接给出结果呢？
/// 上述的序列可以简化为(5 + 6i)(pos = 0),(5 + 6i + 2)(pos=1), (5 + 6i + 4)(pos=2),..
/// pos标记的就是每一块的索引，(5 + 6i)位于索引0， (5 + 6i + 2)位于索引1，(5 + 6i + 4)位于索引2，
/// 位于pos=2的数肯定是奇合数，因为(5 + 6i + 4) = (9 + 6i) = 3 * (3 + 2i),有公因式3存在。
/// pos=0, pos=1,我们需要判断一下是不是合数，减少了三分之一的判断耗时。
#[derive(Clone, Copy, Debug)]
pub struct OddComposite {
    // 从哪里开始查找
    start: u64,
    // 分块内部的索引
    pos: Pos,
}

impl OddComposite {
    /// 找出start这个数所在哪个块 (start - 5) / 6.0 的整数部分就是所在的块i  然后 （start - (5 + 6 * i)）/ 2就是得出所在块的索引
    /// 简化一下： (start - 5) / 6.0 = i + f; i表示整数部分，f表示小数部分 则start = 6i + 6f + 5, 带入上式子有 (6i + 6f + 5 - (5 + 6i))/ 2
    /// = 3f, 索引就是小数部分的3倍，而且由(5 + 6i),(5 + 6i + 2), (5 + 6i + 4),...得小数部分只能是2/6或4/6
    /// `start`:必须至少应该是一个奇数
    /// # Panics: `start`不是一个大于等于5的奇数将引发异常。
    pub fn new(start: u64) -> Self {
        debug_assert!(start >= 5 && start % 2 != 0); // 保证是一个大于等于5的奇数
        let block = (start - 5) as f64 / 6.0;
        let p = (block.fract() * 3.0).round() as u64;
        // p的内存布局和Pos一样
        let pos = unsafe { std::mem::transmute::<_, Pos>(p) };
        Self { start, pos }
    }

    #[allow(unused)]
    #[inline]
    pub fn start(&self) -> u64 {
        self.start
    }

    #[inline]
    pub fn pos(&self) -> Pos {
        self.pos
    }

    /// 获取下一个奇合数,超过u64表示的数值最大值时返回None。
    #[inline(always)]
    pub fn get_next(&mut self) -> Option<u64> {
        loop {
            let current_pos: u64 = self.pos().into();
            let new_pos = (current_pos + 1) % 3;
            self.pos = new_pos.into();
            self.start = self.start.checked_add(2)?; // 数据溢出返回None
            if self.is_odd_composite() {
                return Some(self.start); // 找到了退出
            }
        }
    }

    /// 判断当前的是否是一个奇合数
    #[inline(always)]
    pub fn is_odd_composite(&self) -> bool {
        // 利用pos进行判断
        if self.pos.is_two() {
            return true;
        }

        if Self::is_prime(self.start) {
            return false;
        }

        true
    }

    // 判断一个数是不是素数,使用平方根法，从2到平方根之间的任何一个整数能整除`number`的话，改数不是素数
    // 否则，改数是一个素数。这里使用一个技巧：(5 + 6i)分块形式， 例如i=0为 5,6,7,8,9,10,因为偶数有因子2，
    // （5+6i+4）= 3(3 + 2i)有因子3，所以我们只要测试取模(5+6i)和(5+6i+2)就可以了。
    fn is_prime(number: u64) -> bool {
        if number < 2 {
            return false;
        }

        if number <= 3 {
            return true;
        }

        if number % 2 == 0 || number % 3 == 0 {
            return false;
        }

        let sqrt_num = (number as f64).sqrt() as u64;
        for i in (5..=sqrt_num).step_by(6) {
            if number % i == 0 || number % (i + 2) == 0 {
                return false;
            }
        }
        true
    }

    // 判断奇合数能否分解成一个素数和一个2倍平方和
    #[inline(always)]
    fn factorization(oddc: u64) -> bool {
        let mut index = 1;
        loop {
            let t = (index * index) << 1;
            if t > oddc {
                break;
            }
            let dif = oddc - t;
            if dif > 1 {
                if Self::is_prime(dif) {
                    return true;
                }
            } else {
                // dif == 1
                return false;
            }
            index += 1;
        }
        false
    }
}

impl Iterator for OddComposite {
    type Item = u64;

    #[inline(always)]
    fn next(&mut self) -> Option<Self::Item> {
        loop {
            let oddc = self.get_next()?;
            if !Self::factorization(oddc) {
                return Some(oddc);
            }
        }
    }
}

//----------------------------------------------------------------------------------
#[derive(Debug, Clone, Copy, PartialEq, PartialOrd)]
#[repr(u64)]
pub enum Pos {
    Zero,
    One,
    Two,
}

impl Pos {
    #[inline(always)]
    fn is_two(&self) -> bool {
        *self == 2_u64
    }
}

// u64 -> Pos 保证value的范围<=2
impl From<u64> for Pos {
    #[inline(always)]
    fn from(value: u64) -> Self {
        unsafe { std::mem::transmute(value) }
    }
}

// Pos -> u64
impl From<Pos> for u64 {
    #[inline(always)]
    fn from(value: Pos) -> Self {
        value as u64
    }
}

// Pos类型和usize比较
impl PartialEq<u64> for Pos {
    #[inline(always)]
    fn eq(&self, other: &u64) -> bool {
        *self as u64 == *other
    }
}

impl PartialOrd<u64> for Pos {
    #[inline(always)]
    fn partial_cmp(&self, other: &u64) -> Option<std::cmp::Ordering> {
        Some((*self as u64).cmp(other))
    }
}
//----------------------------------------------------------------------------------
